import java.util.Scanner;

public class maxUncrossLines {
    /**起初两个数组之间的最大不相交的连线的个数
     * 比如： 1 4 2
     *       1 2 4
     * 这里的最长不相交的连线的个数就是2.说白了就是两个数组之间的最长公共子序列的问题
     */
    public static int maxCross(int []nums1,int []nums2){
        // 计算长度
        int len1= nums1.length;
        int len2= nums2.length;
        // 1. 定义dp数组，表示长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
        int[][]dp=new int[len1+1][len2+1];
        // 遍历
        for(int i=1;i<len1+1;i++){
            for (int j=1;j<len2+1;j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.print("请输入数组1的长度：");
        int n1=in.nextInt();

        int []a=new int[n1];
        System.out.print("请依次输入数组1中的元素：");
        for(int i=0;i<n1;i++){
            a[i]=in.nextInt();
        }

        System.out.print("请输入数组2的长度：");
        int n2=in.nextInt();

        int []b=new int[n2];
        System.out.print("请依次输入数组1中的元素：");
        for(int i=0;i<n2;i++){
            b[i]=in.nextInt();
        }

        System.out.println("最长的子序列长度为："+maxCross(a,b));

    }

}
